//给定 m 个数组，每个数组都已经按照升序排好序了。 
//
// 现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。 
//
// 返回最大距离。 
//
// 示例 1： 
//
// 
//输入：[[1,2,3],[4,5],[1,2,3]]
//输出：4
//解释：
//一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。
// 
//
// 示例 2： 
//
// 
//输入：arrays = [[1],[1]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// m == arrays.length 
// 2 <= m <= 10⁵ 
// 1 <= arrays[i].length <= 500 
// -10⁴ <= arrays[i][j] <= 10⁴ 
// arrays[i] 以 升序 排序。 
// 所有数组中最多有 10⁵ 个整数。 
// 
//
// 
//
// Related Topics 贪心 数组 👍 122 👎 0


package LeetCode.editor.cn;


import java.util.List;

/**
 * @author ldltd
 * @date 2025-02-19 09:44:03
 * @description 624.数组列表中的最大距离
 
 */
 
public class MaximumDistanceInArrays {
    public static void main(String[] args) {
    //测试代码
    MaximumDistanceInArrays fun = new MaximumDistanceInArrays();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //枚举每一个子数组，从里面取最大最小的那一个，但是可能最后的结果是取得同一个子数组中的
    //每次遍历记录最大值和最小值，且每个子数组的第一和最后都需要和前面的最大最小分别取差值，防止最后一次取差值时来自同一个数组
    //遍历结束后可以保证最大值一定和除自己以外的最小值取过差值，同理最小值一定和除自己以外的最大值取过差值

    public int maxDistance(List<List<Integer>> arrays) {
        int min=arrays.get(0).get(0);
        int max=arrays.get(0).get(arrays.get(0).size()-1);
        int res=0;
        for (int i = 1; i < arrays.size(); i++) {
            //因为res取值是和历史的max 和 min比较，所以res一定是来自不同数组之间的差值
            res= Math.max(res,Math.abs(arrays.get(i).get(arrays.get(i).size()-1)-min));
            res= Math.max(res,Math.abs(max-arrays.get(i).get(0)));
            max=Math.max(max,arrays.get(i).get(arrays.get(i).size()-1));
            min=Math.min(min,arrays.get(i).get(0));
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
